1. Field of the Invention
The present invention relates to computer networks and more particularly to managing paths for probe packets transferred in a computer network.
2. Background Information
A computer network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end nodes, such as personal computers and workstations (“hosts”). Many types of networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect the nodes over dedicated private communications links located in the same general physical location, such as a building or campus. WANs, on the other hand, typically connect geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines, optical lightpaths, synchronous optical networks (SONET), or synchronous digital hierarchy (SDH) links. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other. Computer networks may be further interconnected by an intermediate network node, such as a router, to extend the effective “size” of each network.
Since management of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as routing domains or autonomous systems. The networks within an autonomous system (AS) are typically coupled together by conventional “intradomain” routers configured to execute intradomain routing protocols, and are generally subject to a common authority. To improve routing scalability, a service provider (e.g., an ISP) may divide an AS into multiple “areas.” It may be desirable, however, to increase the number of nodes capable of exchanging data; in this case, interdomain routers executing interdomain routing protocols are used to interconnect nodes of the various ASes. Moreover, it may be desirable to interconnect various ASes that operate under different administrative domains. As used herein, an AS or an area is generally referred to as a “domain,” and a node that interconnects different domains together is generally referred to as a “border node or border router.” In general, the autonomous system may be an enterprise network, a service provider or any other network or subnetwork. Furthermore, the autonomous system may be multi-homed, i.e., comprising a plurality of different peer (neighboring) connections to one or more other routing domains or autonomous systems.
The administrative entity of an AS typically configures network nodes within the AS to route packets using predetermined intradomain routing protocols, or interior gateway protocols (IGPs), such as conventional link-state protocols and distance-vector protocols. These IGPs define the manner with which routing information and network-topology information is exchanged and processed in the AS. Examples of link-state and distance-vectors protocols known in the art are described in Sections 12.1-12.3 of the reference book entitled Interconnections, Second Edition, by Radia Perlman, published January 2000, which is hereby incorporated by reference as though fully set forth herein.
Link-state protocols, such as the Open Shortest Path First (OSPF) protocol, use cost-based routing metrics to determine how data packets are routed in an AS. As understood in the art, a relative cost value may be associated with a network node to determine the relative ease/burden of communicating with that node. For instance, the cost value may be measured in terms of the average time for a data packet to reach the node, the amount of available bandwidth over a communication link coupled to the node, etc. Network nodes in the AS generate a set of cost values associated with their neighboring nodes. Each set of cost values is then “advertised” (flooded) to the other interconnected nodes. Using the advertised cost values, each node can generate a consistent “view” of the network topology, thereby enabling the nodes to determine lowest-cost routes within the AS.
Distance-vector protocols, such as the Interior Gateway Routing Protocol (IGRP) or Routing Information Protocol (RIP), use distance-based routing metrics to determine how data packets are routed in an AS. A network node may associate a distance metric with each of its interconnected nodes in the AS. For example, the distance metric may be based on, e.g., a number of hops between a pair of nodes or an actual distance separating the nodes. Operationally, the network nodes determine distances to reachable nodes in the AS and communicate these distance metrics to their neighboring nodes. Each neighboring node augments the received set of distance metrics with its own distance measurements and forwards the augmented set of metrics to its neighbors. This process is continued until each node receives a consistent view of the network topology.
A plurality of interconnected ASes may be configured to exchange routing and reachability information among neighboring interdomain routers of the systems in accordance with a predetermined external gateway protocol, such as the Border Gateway Protocol (BGP). The BGP protocol is well known and generally described in Request for Comments (RFC) 1771, entitled A Border Gateway Protocol 4 (BGP-4), published March 1995, which is hereby incorporated by reference in its entirety. An adjacency is a relationship formed between selected neighboring (peer) routers for the purpose of exchanging routing information messages and abstracting the network topology. The routing information exchanged by BGP peer routers typically includes destination address prefixes, i.e., the portions of destination addresses used by the routing protocol to render routing (“next hop”) decisions. Examples of such destination addresses include IP version 4 (IPv4) and version 6 (IPv6) addresses. BGP generally operates over a reliable transport protocol, such as TCP, to establish a TCP connection/session. The BGP protocol facilitates policy-based routing in which an administrative entity places restrictions on inter-AS routing operations. For example, the administrator of a company's AS may employ a routing policy where network traffic leaving the AS is not permitted to enter a competitor's network, even if the competitor provides an otherwise acceptable routing path. To implement the BGP protocol, each AS includes at least one border node through which it communicates with other, interconnected ASes. Because data packets enter and exit the AS through the border node, the border node is said to be located at the “edge” of the AS.
An intermediate network node often stores its routing information in a routing table maintained and managed by a routing information base (RIB). The routing table is a searchable data structure in which network addresses are mapped to their associated routing information. However, those skilled in the art will understand that the routing table need not be organized as a table, and alternatively may be another type of searchable data structure. Although the intermediate network node's routing table may be configured with a predetermined set of routing information, the node also may dynamically acquire (“learn”) network routing information as it sends and receives data packets. When a packet is received at the intermediate network node, the packet's destination address may be used to identify a routing table entry containing routing information associated with the received packet. Among other things, the packet's routing information indicates the packet's next-hop address.
In some networks, border nodes located at edges of ASes, e.g., between an enterprise network and one or more Internet Service Providers (ISPs), may be configured as Optimized Edge Routers (OERs). Here each OER may be configured to periodically select an Optimal Exit Link (OEL) to each ISP for a given destination prefix (a monitored prefix) based on performance, load, cost, and service level agreements (SLAs) associated with connections to the ISP. Ultimately, the end result for the enterprise network is improved Internet performance, better load distribution, and/or lower costs for Internet connections. Techniques that may be used to select the OEL for the monitored prefix include passive monitoring and/or active probing. Passive monitoring relies on gathering information from OERs learned from monitoring conventional user traffic, such as throughput, timing, latency, packet loss, reachability, etc. Active probing, on the other hand, relies on probe packets to measure various parameters associated with accessing the monitored prefix from an originating node (source). Here, the originating node may generate multiple probe packets that are then forwarded via different exits (e.g., data links) on different paths to target nodes (targets) in the monitored (destination) prefix. Upon receiving the probe packets, the targets respond to the originating node, e.g., with return packets or other known probe responses. The originating node may eventually acquire the responses and use them to measure various parameters, such as delay, loss, jitter, and reachability, etc., associated with accessing the destination prefix via the different links. The originating node may then use the parametric (performance) information (i.e., learned from passive monitoring or active probing) to select an OEL from among the different exits that may be used to reach the destination prefix.
The accuracy of active probing, however, may be influenced by several factors. In conventional networks, for instance, the RIB typically uses its routing table to select the exits for the probe packets based on the destination of the target. This limits the ability of the probe packets to measure parametric information correlated with particular exits of the source. Also, in conventional networks, returned probe response packets may not be forwarded directly to the source and instead may be forwarded to a node within the same prefix as the source that generally receives traffic for that prefix. Often, the source address used in the probe packets may not be an address that uses the same routing policy and/or path of user data. Some destination prefixes (or intermediate domains) may, in fact, drop a probe packet in transit based on the particular exit used, such as when based on certain policy decisions. In order to obtain parametric information that closely matches an expected performance with user data, the path taken by the probe packets should closely match the routing policy/path of user data.